/*
 * @lc app=leetcode.cn id=1124 lang=javascript
 *
 * [1124] 表现良好的最长时间段
 */

// @lc code=start
/**
 * @param {number[]} hours
 * @return {number}
 */
var longestWPI = function (hours) {
  const size = hours.length;
  // 前缀和
  const presum = new Array(size + 1).fill(0);

  for (let i = 0; i < size; i++) {
    if (hours[i] > 8) {
      presum[i + 1] = presum[i] + 1;
    } else {
      presum[i + 1] = presum[i] - 1;
    }
  }

  // 下标i的前缀和要尽可能的小，这里用单调递减栈
  let stack = [];
  for (let i = 0; i < presum.length; i++) {
    if (stack.length === 0 || presum[stack[stack.length - 1]] > presum[i]) {
      stack.push(i);
    }
  }

  let result = 0;
  let j = size;
  // 倒序遍历，当preSum[j]>preSum[i]的时候，更新结果，直到栈中的i全部遍历完毕
  while (j > result) {
    while (stack.length && presum[stack[stack.length - 1]] < presum[j]) {
      result = Math.max(result, j - stack.pop());
    }
    j--;
  }

  return result;
};
// @lc code=end
